#include <stdio.h>
#include <math.h>

#include "probleme.h"
#define LONGUEUR_LIGNE 10
//#define _VERBOSE_

/**  Fonction  initProbleme
 *   Crée et initialise une instance de problème à partir d'un fichier texte.
 *
 *   Paramètre:
 *              char *nomFichierDescriptif  : le nom du fichier à lire.
 * 
 *   Retourne:
 *              Probleme * : un pointeur sur le nouveau problème
 *
 *              NULL : si la lecture échoue.
 *
 *
 */


Probleme *initProbleme(char *nomFichierDescriptif) {
    printf("Initialisation du problème...\n");

    char buffer[20];
    FILE *f;

    f = fopen(nomFichierDescriptif, "r");
    if (f == NULL)
        return NULL;

    Probleme *p = (Probleme *) malloc(sizeof (Probleme));
    p->enonceProbleme = NULL;
    p->nomFichierSortie = NULL;
    p->etatInitial = NULL;
    p->etatFinal = NULL;
    p->etatCourant = NULL;

    fgets(buffer, 20, f);
    p->nomFichierSortie = buffer;

    printf("%s", p->nomFichierSortie);
    return p;

}

/**  Procédure imprimerEnonceProbleme
 *   Imprime sur le fichier de sortie l'enoncé du problème
 *   Si le fichier de sortie n'a pas été défini l'impression a lieu sur stdout


 *   Paramètre:
 *              Probleme *p : le problème à traiter.
 * 
 *
 */


void imprimerEnonceProbleme(Probleme *p) {
}

/**  Fonction  premierEtat
 *   Calcule dans le contexte du problème donné l'état initial de la recherche par énumération
 *
 *   Paramètre:
 *              Probleme *p : le contexte à traiter
 * 
 *   Retourne:
 *              Etat * : le premier etat recherché
 *
 */



Etat *premierEtat(Probleme *p, char* nomFichierDescriptif) {

    printf("Initialisation du premier état...\n");
    Etat *e;
    int j, i, k, l, m, n, o, t, q, r, s = 0, compteurGrilleComplete = 0, compteurLignes = 0, compteurColonnes = 0;
    k = l = m = n = o = t = q = r = s = 0;
    char buffer[LONGUEUR_LIGNE];
    char flusher[20];
    FILE *f;



    f = fopen(nomFichierDescriptif, "r");
    if (f == NULL)
        return NULL;

    fgets(flusher, 20, f);

    e = (Etat *) malloc(sizeof (Etat));



    while (fgets(buffer, LONGUEUR_LIGNE, f) != NULL) {

        for (j = 0; j < 9; j++) {
            e->grilleComplete[compteurGrilleComplete] = buffer[j] - 48;
/*
            e->lignes[compteurLignes][j] = buffer[j] - 48;
            e->colonnes[j][compteurColonnes] = buffer[j] - 48;
*/
            compteurGrilleComplete++;
        }
/*
        compteurLignes++;
        compteurColonnes++;
*/

        fgets(flusher, 2, f);
    }

    for (j = 0; j < 9; j++) {
        for (i = 0; i < 9; i++) {
            e->lignes[j][i]=e->grilleComplete+i+j*9;
            e->colonnes[i][j]= e->grilleComplete+i+j*9;
        }
    }

    for (j = 0; j < 9; j++) {
        for (i = 0; i < 9; i++) {
            switch (j % 3) {
                case 0:
                    switch (i % 3) {
                        case 0: e->sousGrilles[k][0] = e->lignes[j][i];
                            k++;
                            break;
                        case 1: e->sousGrilles[l][1] = e->lignes[j][i];
                            l++;
                            break;
                        case 2: e->sousGrilles[m][2] = e->lignes[j][i];
                            m++;
                            break;
                    }
                    break;
                case 1:
                    switch (i % 3) {
                        case 0: e->sousGrilles[n][3] = e->lignes[j][i];
                            n++;
                            break;
                        case 1: e->sousGrilles[o][4] = e->lignes[j][i];
                            o++;
                            break;
                        case 2: e->sousGrilles[t][5] = e->lignes[j][i];
                            t++;
                            break;
                    }
                    break;
                case 2:
                    switch (i % 3) {
                        case 0: e->sousGrilles[q][6] = e->lignes[j][i];
                            q++;
                            break;
                        case 1: e->sousGrilles[r][7] = e->lignes[j][i];
                            r++;
                            break;
                        case 2: e->sousGrilles[s][8] = e->lignes[j][i];
                            s++;
                            break;
                    }
                    break;
            }


        }


    }

    for (j = 0; j < 81; j++) {
        if (e->grilleComplete[j] == 0)  {
            
            for (i=0; i<9; i++) {
                e->possibilitesGrille[j][i] = i+1;
            }
    
        }
        else    {
            for (i=0; i<9; i++) {
                e->possibilitesGrille[j][i] = 0;
            }
        }
           
    }
    
#ifdef _VERBOSE_
      printf("Grille complète : \n");
      puts("----------");
      for (compteurGrilleComplete=0;compteurGrilleComplete<81;compteurGrilleComplete++)    {
          printf("%d", e->grilleComplete[compteurGrilleComplete]);
          if(compteurGrilleComplete%9 == 8)
              printf("\n");
      }
      puts("Fin de la grille complète----------");

      printf("Grille lignes : \n");
      puts("----------");
      for (compteurLignes=0;compteurLignes<9;compteurLignes++)    {
          for (j=0;j<9;j++)    {
          printf("%d", *e->lignes[compteurLignes][j]);
          }
          printf("\n");
      }
      puts("Fin de la grille lignes----------");

      printf("Grille colonnes : \n");
      puts("----------");
      for (compteurColonnes=0;compteurColonnes<9;compteurColonnes++)     {
          for (j=0;j<9;j++)    {
          printf("%d", *e->colonnes[j][compteurColonnes]);
          }
          printf("\n");
      }
      puts("Fin de la grille colonnes----------");

      printf("Grille sous-grille : \n");
      puts("----------");
      for (compteurColonnes=0;compteurColonnes<9;compteurColonnes++)     {
          for (j=0;j<9;j++)    {
          printf("%d", *e->sousGrilles[compteurColonnes][j]);
          }
          printf("\n");
      }
      puts("Fin de la grille sous-grille----------");
#endif

    printf("Premier Etat initialisé...\n");
    return e;
}

/**  Fonction  estSolution 
 *   Teste si un Etat e est une solution du Probleme p 
 *
 *   Paramètres:
 *              Probleme *p : le problème considéré
 *
 *              Etat *e :   l'état qui une solution potentielle.
 * 
 *   Retourne:
 *              1: si l'Etat e est une solution du Probleme p
 *              0: sinon.
 */



int estSolution(Probleme *p, Etat *e) {
    int i = 0;
    for (i = 0; i < 9; i++) {
        if (existeDoublonOuZero(*e->colonnes[i]) == 1 || existeDoublonOuZero(*e->lignes[i]) == 1 || existeDoublonOuZero(*e->sousGrilles[i]) == 1)
            return 0;
    }
    return 1;
}

/**  Fonction  estEchec
 *   Teste si  une solution potentielle du Probleme p  peut être construite à partir d'un Etat e. 
 *
 *   Paramètres:
 *              Probleme *p : le problème considéré
 *
 *              Etat *e :   l'état considéré
 * 
 *   Retourne:
 *              1: si aucune solution du Probleme p ne peut être construite à partir de l'Etat e.
 *              0: sinon. 
 */


int estEchec(Probleme *p, Etat *e) {
    int i = 0;
    for (i = 0; i < 9; i++) {
        if (existeDoublonOuZero(*e->colonnes[i]) == 1 || existeDoublonOuZero(*e->lignes[i]) == 1 || existeDoublonOuZero(*e->sousGrilles[i]) == 1)
            return 1;
    }
    return 0;
}
void removeAllPossibilitiesBut (Etat* stateToFollow, int index, int value)  {

    int i;
    for (i=0;i<9;i++)   {
        if (i != value-1)
        stateToFollow->possibilitesGrille[index][i] =0;
    }


}
//ATTENTION LES PARAMETRES DOIVENT ETRE TRANSMIS DANS L'ORDRE !!!
void threesComplement (Etat* stateTofFollow, int* group1[9], int* group2[9], int* group3[9],int groupNumber, int hintIndex)   {
//hint = 0 <=> colonne
    //hint = 1 <=>ligne
    int i,j,k;
    int gridNumber1, gridNumber2, gridNumber3, indexInFullGrid, possibilitiesCounter=0;
    for (i=0;i<9;i++)   {

        for (j=0;j<9; j++)  {
            //CAS 1
            if (*group1[i]==*group2[j] && *group1[i] != 0) {
                if (isOnTheGroup(*group3,*group1[i])==0)    {
                    if (hintIndex == 1) {
                       gridNumber1 = getUnderGridNumber(groupNumber*9+i); //Concerne group1
                       gridNumber2 = getUnderGridNumber((groupNumber+1)*9+i); //concerne Groupe 2
                    }
                    else {
                        gridNumber1 = getUnderGridNumber(i*9+groupNumber); //Concerne group1
                       gridNumber2 = getUnderGridNumber(i*9+(groupNumber+1)); //concerne Groupe 2
                    }
                   if (abs(gridNumber2-gridNumber1) < 3 )   { //Cas de la 3è ligne
                      gridNumber3 = (21 - gridNumber2 -gridNumber1) % 9 ;
                      for (k=6;k<9;k++) {
                          // Trouve l'index dans la grille complète à partir de l'indice dans la sous grille et du numéro de sous grille
                          indexInFullGrid = (gridNumber3/3) * 27 + 3 * (gridNumber3%3) + (k/3) * 9 + k%3;
                          if (stateTofFollow->possibilitesGrille[indexInFullGrid][*group1[i]-1] != 0) {
                              possibilitiesCounter ++;
                          }
                      }
                      if (possibilitiesCounter==1)  {
                          removeAllPossibilitiesBut(stateTofFollow,indexInFullGrid,*group1[i]-1);
                      }

                   }
                   else { //Cas de la 3è colonne
                      gridNumber3 = (15-i-j)-3*(2-i%3);
                      for (k=2;k<9;k+=3) {
                          // Trouve l'index dans la grille complète à partir de l'indice dans la sous grille et du numéro de sous grille
                          indexInFullGrid = (gridNumber3/3) * 27 + 3 * (gridNumber3%3) + (k/3) * 9 + k%3;
                          if (stateTofFollow->possibilitesGrille[indexInFullGrid][*group1[i]-1] != 0) {
                              possibilitiesCounter ++;
                          }
                      }
                      if (possibilitiesCounter==1)  {
                          removeAllPossibilitiesBut(stateTofFollow,indexInFullGrid,*group1[i]-1);
                      }
                   }

                }
            }
            //CAS 2
            else if (*group2[i]==*group3[j] && *group2[i] != 0) {
                if (isOnTheGroup(*group1,*group2[i])==0)    { //g2 & g3
                    if (hintIndex == 1) {
                       gridNumber1 = getUnderGridNumber((groupNumber+1)*9+i); //Concerne group2
                       gridNumber2 = getUnderGridNumber((groupNumber+2)*9+i); //concerne Groupe 3
                    }
                    else {
                        gridNumber1 = getUnderGridNumber(i*9+groupNumber+1); //Concerne group2
                       gridNumber2 = getUnderGridNumber(i*9+(groupNumber+2)); //concerne Groupe 3
                    }
                   if (abs(gridNumber2-gridNumber1) < 3 )   { //Cas de la 3è ligne
                      gridNumber3 = (21 - gridNumber2 -gridNumber1) % 9 ;
                      for (k=6;k<9;k++) {
                          // Trouve l'index dans la grille complète à partir de l'indice dans la sous grille et du numéro de sous grille
                          indexInFullGrid = (gridNumber3/3) * 27 + 3 * (gridNumber3%3) + (k/3) * 9 + k%3;
                          if (stateTofFollow->possibilitesGrille[indexInFullGrid][*group2[i]-1] != 0) {
                              possibilitiesCounter ++;
                          }
                      }
                      if (possibilitiesCounter==1)  {
                          removeAllPossibilitiesBut(stateTofFollow,indexInFullGrid,*group2[i]-1);
                      }

                   }
                   else { //Cas de la 3è colonne
                      gridNumber3 = (15-i-j)-3*(2-i%3);
                      for (k=0;k<9;k+=3) {
                          // Trouve l'index dans la grille complète à partir de l'indice dans la sous grille et du numéro de sous grille
                          indexInFullGrid = (gridNumber3/3) * 27 + 3 * (gridNumber3%3) + (k/3) * 9 + k%3;
                          if (stateTofFollow->possibilitesGrille[indexInFullGrid][*group2[i]-1] != 0) {
                              possibilitiesCounter ++;
                          }
                      }
                      if (possibilitiesCounter==1)  {
                          removeAllPossibilitiesBut(stateTofFollow,indexInFullGrid,*group2[i]-1);
                      }
                   }

                }
            }
            //CAS 3
            else if (*group1[i]==*group3[j] && *group1[i] != 0) {
                if (isOnTheGroup(*group2,*group1[i])==0)    { //G1 && g3
                    if (hintIndex == 1) {
                       gridNumber1 = getUnderGridNumber((groupNumber)*9+i); //Concerne group1
                       gridNumber2 = getUnderGridNumber((groupNumber+2)*9+i); //concerne Groupe 3
                    }
                    else {
                        gridNumber1 = getUnderGridNumber(i*9+groupNumber); //Concerne group1
                       gridNumber2 = getUnderGridNumber(i*9+(groupNumber+2)); //concerne Groupe 3
                    }
                   if (abs(gridNumber2-gridNumber1) < 3 )   { //Cas de la 3è ligne
                      gridNumber3 = (21 - gridNumber2 -gridNumber1) % 9 ;
                      for (k=6;k<9;k++) {
                          // Trouve l'index dans la grille complète à partir de l'indice dans la sous grille et du numéro de sous grille
                          indexInFullGrid = (gridNumber3/3) * 27 + 3 * (gridNumber3%3) + (k/3) * 9 + k%3;
                          if (stateTofFollow->possibilitesGrille[indexInFullGrid][*group1[i]-1] != 0) {
                              possibilitiesCounter ++;
                          }
                      }
                      if (possibilitiesCounter==1)  {
                          removeAllPossibilitiesBut(stateTofFollow,indexInFullGrid,*group1[i]-1);
                      }

                   }
                   else { //Cas de la 3è colonne
                      gridNumber3 = (15-i-j)-3*(2-i%3);
                      for (k=1;k<9;k+=3) {
                          // Trouve l'index dans la grille complète à partir de l'indice dans la sous grille et du numéro de sous grille
                          indexInFullGrid = (gridNumber3/3) * 27 + 3 * (gridNumber3%3) + (k/3) * 9 + k%3;
                          if (stateTofFollow->possibilitesGrille[indexInFullGrid][*group1[i]-1] != 0) {
                              possibilitiesCounter ++;
                          }
                      }
                      if (possibilitiesCounter==1)  {
                          removeAllPossibilitiesBut(stateTofFollow,indexInFullGrid,*group1[i]-1);
                      }
                   }

                }


            }
        }

    }



}


/**  Fonction  etatSuivant
 *   Produit une suite "exhaustive" minimale d'extensions de l'état e  dans le contexte du problème p.
 *   
 *   Une état e' est une extension d'un état e si e' est déduit de e en ajoutant une ou plusieurs condition(s) supplémentaires.  
 *
 *   Une suite d'extensions états (e1, e2, .. eN) d'un état e est dite "exhaustive" si extension de l'état e est:
 *             1) Soit un des états e1, e2, .. en
 *             2) Soit une extension de l'un de ces états
 *  
 *
 *   Une suite exhaustive s=(e1, e2, .. eN) d'extensions d'un état e est dite minimale 
 *   si toute s' obtenue à partir de s en retirant l'un quelconque des états e1, e2, ...  eN n'est plus exhaustive. 
 *
 *
 *    Dans le contexte d'un problème p un état e admet en général plusieurs suites exhaustives minimales d'extensions.
 *    Le choix d'une de ces suites correspond donc à un choix d'une stratégie d'énumération qui est implémenté dans la fonction.  
 *
 * 
 *    En outre, l'ordre des états e1, e2, ...  eN  constitue un autre choix stratégique qui peut être important lors de la recherche d'une seule solution
 *
 *
 *    Paramètres:
 *
 *              Probleme *p :  Le problème qui sert de contexte
 *          
 *              Etat *e : L 'Etat dont on veut connaître les extensions possibles
 * 
 *    Retourne:
 *              Etat * : La première extension de l'état e.
 *
 *    Pour obtenir toutes les extensions d' un etat e dans le contexte d'un problème p, il faut procéder de la manière suivante:
 *           1) Appeler etatSuivant(p, e) --> e1
 *
 *           2) Appeler plusieurs fois etatSuivant(p, NULL) qui renvoie  successivement  les états e2, e3, .. eN
 *    
 *           3) Un appel supplémentaire de la forme etatSuivant(p, NULL) renvoie NULL pour indiquer que toute la suite des extensions de e a été explorée
.*
 *
 *
 */

void construireStrategie(Probleme *p, Etat *etatCourant, Etat* etatSuivant)   {



}


Etat *etatSuivant(Probleme *p, Etat *etatCourant) {
  Etat *e;
  e = (Etat *) malloc(sizeof (Etat));
  if (etatCourant != NULL)
    construireStrategie(p, etatCourant, e);
}


int preSolve (Etat* etatAModifier) {

    int i,j=0;
    int changementNombre = 0;
    int NbZeros=0;
    int nombreNonNul=-1;

    //Etape 1, check lignes, colonnes, et sous-grilles, cas triviaux
    for (j=0;j<81;j++)  {
        if (etatAModifier->grilleComplete[j] == 0)  {
            for(i=0;i<9;i++)    {
               if ( *etatAModifier->lignes[j/9][i] !=0 )
               etatAModifier->possibilitesGrille[j][*etatAModifier->lignes[j/9][i]-1] = 0;
            }
            for(i=0;i<9;i++)    {
               if ( *etatAModifier->colonnes[j%9][i] !=0 )
               etatAModifier->possibilitesGrille[j][*etatAModifier->colonnes[j%9][i]-1] = 0;
            }
            for(i=0;i<9;i++)    {
               if ( *etatAModifier->sousGrilles[getUnderGridNumber(j)][i] !=0 )
               etatAModifier->possibilitesGrille[j][*etatAModifier->sousGrilles[getUnderGridNumber(j)][i]-1] = 0;
            }

        }
    }



    //Etape finale, on modifie les cases et on compte le nombre de cases modifiées (savoir si on doit recommencer
    for (j=0;j<81;j++)  {
        for(i=0;i<9;i++)    {
            if (etatAModifier->possibilitesGrille[j][i] == 0)
                    NbZeros++;
            else    {
               nombreNonNul = etatAModifier->possibilitesGrille[j][i];
            }
        }
        if (NbZeros == 8)   {
           etatAModifier->grilleComplete[j] = nombreNonNul;
           etatAModifier->possibilitesGrille[j][nombreNonNul-1] = 0;
           changementNombre++;
        }
        NbZeros = 0;
    }




    printf ("Nombre de cases modifiées : %d\n", changementNombre);

    return changementNombre;

}

int preSolve2 (Etat* etatAModifier) {
    int i,j=0;
    int changementNombre = 0;
    int NbZeros=0;
    int nombreNonNul=-1;
    
    //Etape 2 : complément à trois int groupNumber, int hintIndex
   threesComplement(etatAModifier,etatAModifier->lignes[0],etatAModifier->lignes[1],etatAModifier->lignes[2],0,1);
   threesComplement(etatAModifier,etatAModifier->lignes[3],etatAModifier->lignes[4],etatAModifier->lignes[5],3,1);
   threesComplement(etatAModifier,etatAModifier->lignes[6],etatAModifier->lignes[7],etatAModifier->lignes[8],6,1);
   threesComplement(etatAModifier,etatAModifier->colonnes[0],etatAModifier->colonnes[1],etatAModifier->colonnes[2],0,0);
   threesComplement(etatAModifier,etatAModifier->colonnes[3],etatAModifier->colonnes[4],etatAModifier->colonnes[5],3,0);
   threesComplement(etatAModifier,etatAModifier->colonnes[6],etatAModifier->colonnes[7],etatAModifier->colonnes[8],6,0);

     //Etape finale, on modifie les cases et on compte le nombre de cases modifiées (savoir si on doit recommencer
    for (j=0;j<81;j++)  {
        for(i=0;i<9;i++)    {
            if (etatAModifier->possibilitesGrille[j][i] == 0)
                    NbZeros++;
            else    {
               nombreNonNul = etatAModifier->possibilitesGrille[j][i];
            }
        }
        if (NbZeros == 8)   {
           etatAModifier->grilleComplete[j] = nombreNonNul;
           etatAModifier->possibilitesGrille[j][nombreNonNul-1] = 0;
           changementNombre++;
        }
        NbZeros = 0;
    }




    printf ("Nombre de cases modifiées : %d\n", changementNombre);

    return changementNombre;

}

int getUnderGridNumber (int index) {

    int numLigne=index/9;
    int numColonne = index%9;

    if (numLigne<3) {
        if (numColonne<3)
            return 0;
        else if (numColonne<6)
            return 1;
        else
            return 2;

    }
    else if (numLigne<6)    {
        if (numColonne<3)
            return 3;
        else if (numColonne<6)
            return 4;
        else
            return 5;
    }
    else    {
        if (numColonne<3)
            return 6;
        else if (numColonne<6)
            return 7;
        else
            return 8;
    }


}







int isOnTheGroup(int group[9],int j)    {

    int i;
    for (i=0;i<9;i++)   {

        if (group[i] == j)  {
            return 1;
        }
    }

    return 0;
}
/**  Procédure imprimerEtat
 *   Imprime sur le fichier de sortie ne description de l'Etat e.
 *   Si le fichier de sortie n'a pas été défini l'impression a lieu sur stdout
 *
 *
 *   Paramètre:
 *              Etat *e : l'Etat à décrire.
 * 
 *
 */





void imprimerEtat(Probleme *p, Etat *e) {

    int compteurGrilleComplete;


    printf("Grille complète : \n");
    puts("----------");
    for (compteurGrilleComplete = 0; compteurGrilleComplete < 81; compteurGrilleComplete++) {
        printf("%d", e->grilleComplete[compteurGrilleComplete]);
        if (compteurGrilleComplete % 9 == 8)
            printf("\n");
    }
    puts("Fin de la grille complète----------");


}

/**  Procédure  terminerProbleme
 *   Cette procédure effectue deux actions
 *
 *          1) Elle imprime sur le fichier de sortie (ou sur stdout) un compte-rendu de la résolution
 *
 *          2)  Elle libére la mémoire occupée par le problème
 *
 *
 *   Paramètres:
 *             Probleme *p : Le problème  à traiter
 *
 *             int impression : des directives d'impression du compte-rendu.
 *                         0: ne rien imprimer
 *                         1: imprimer le compte-rendu
 *             
 *             char *infos  : Des informations complémentaires fournies par le programme d'appel.
 *                            Ces informations peuvent être utilisées dans le compte-rendu.
 *
 *
 */


void terminerProbleme(Probleme *p, int impression, char *infos) {
}

/**  Fonction   estEgal
 *   Cette fonction teste si deux états états sont égaux dans le contexte du problème p.
 *
 *
 *
 *
 *   Paramètres:
 *             Probleme *p : Le problème  à traiter
 *
 *             Etat *e1
 *             Etat *e2
 *   
 *                       Les états à comparer.
 *
 *    Retourne 1 : si les états sont égaux.
 *             0: sinon.
 *
 */

int estEgal(Probleme *p, Etat *e1, Etat *e2) {
    int i;
    for(i=0;i<81;i++){
        if(e1->grilleComplete[i] != e2->grilleComplete[i])
            return 0;
    }
    return 1;
}

int isFilled (Etat* stateToRead, int index) {

    int i;
    for (i=0; i<9; i++) {

        if (stateToRead->possibilitesGrille[index][i] !=0)  {
            return 0;
        }
    }
    return 1;

}


int existeDoublonOuZero(int tab[9]) {

    int i, j = 0;

    for (i = 0; i < 9; i++) {
        if (tab[i] == 0)
            return 1;
        for (j = 0; j < i; j++) {
            if (tab [i] == tab[j])
                return 1;
        }

    }

    return 0;

}



/** Fonction   libererEtat
 *  détruit un état et récupère correctement la mémoire correspondante
 *  La signature  attendue serait de la forme
 *
 *  void libererEtat(Etat *e) ;
 *   où e est l'etat à supprimer
 *
 *  En fait  on utilise une une macro pour garder l'encapsulation tout en
 *  évitant la lourdeur d'un appel de fonction
 *
 *  Attention la macro doit être redéfinie lorsque la structure précise de la structure Etat a été modifiée
 */


//void libererEtat(Etat *e){ ;
//}


